home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 21 / Cream of the Crop 21 (Terry Blount) (October 1996).iso / program / qsort2.zip / QSORT2.JAV
Text File  |  1996-08-18  |  10KB  |  278 lines
  1. /////////////////////////////////////////////////////////////////////////////
  2. /** This routine Quicksorts two arrays. The first array (called KWList here)
  3. is actively sorted while the second (called KWPtr here) is passive: it moves
  4. with its corresponding element in the active array. An example is sorting of
  5. full names but based on Last names only, so the input file may look like
  6.  
  7. Dover, Ben
  8. Freely, I.P.
  9. Tuhuggenkiss, Amanda
  10. Liball, Bo
  11. Graham, Anna
  12. Dozent, Betty
  13. ...
  14.  
  15. Illustrates usage of linked lists(vectors), DOS file IO, and the
  16. StringTokenizer.
  17.  
  18. input is a text file of two columns of strings (arbitrary length & number)
  19. The two columns must be blank delimited.
  20. Output is the sorted version of input.
  21. All data is converted to uppercase before sorting and output.
  22.  
  23. This routine was translated from the Numerical Recipes book by Press et al.
  24. by a java ultra-novice:
  25. Y.T. Tim Hatamian, Mathematicus Laboratories
  26.                    73243.647@compuserve.com
  27.                    Ourworld.Compuserve.com/Homepages/Mathematicus
  28.  
  29. Please let me know of any problems.*/
  30. /////////////////////////////////////////////////////////////////////////////
  31.         
  32.  
  33. //package Scriptis.Util;       //Scriptis Utilities
  34. import java.io.*;
  35. import java.util.*;
  36.  
  37. public class Sort2{
  38.     private static Vector KWList = new Vector(50,50);     //Text of 1st arrray
  39.     private static Vector KWPtr = new Vector(50,50);      // 2nd array
  40.     private static int KWNumber;                          //# of elements in each array
  41.  
  42.     public static void main(String args[]){
  43.       String outfile,infile;
  44.         
  45.       try {infile = args[0];}
  46.       catch (IndexOutOfBoundsException e) {
  47.              System.out.println("Usage: java Sort2 <inputfile>   (overwrites input)");
  48.              System.out.println(" or :  java Sort2 <inputfile> <outputfile> ");
  49.              System.exit(0);
  50.       }
  51.  
  52.       infile=args[0];  
  53.       try { outfile = args[1]; }
  54.       catch (IndexOutOfBoundsException e) { outfile = infile; }
  55.  
  56.  
  57.       GetKWs(infile);                            //load input into vectors
  58.       QuickSort2();                                 //use quicksort algorithm
  59.       WriteKWs(outfile);                        // Write sorted list
  60.  
  61.     }   //end main
  62.         
  63.  
  64. //=========================================================================
  65. /** Quicksort from Numerical recipes; translated from Fortran.
  66. TEMPA1 and TEMPB1 have been added to cope with the Java's cumbersome notation.
  67. Note: this routine requires 1 based arrays(vectors)
  68. */
  69.     static void QuickSort2(){
  70.         int m=7,nstack=100;
  71.         String a,b,tempa,tempb,tempa1,tempb1;    //scrtach pads for 1st&2nd array elemnts
  72.         int i,j,k,ir=KWNumber,jstack=0,l=1;
  73.         int istack[]=new int[nstack];
  74.         boolean goto2=false,loop3=true;                   //need these for branching
  75.       
  76.         while (true){
  77.           if(ir-l < m){
  78.  
  79.             for(j=l+1;j<=ir;j++){           //loop-12
  80.               a=KWList.elementAt(j).toString();
  81.               b=KWPtr.elementAt(j).toString();
  82.               for(i=j-1;i>=1;i--){           //loop-11
  83.                 tempa1=KWList.elementAt(i).toString();
  84.                 tempb1=KWPtr.elementAt(i).toString();
  85.                 if(tempa1.compareTo(a)<=0){goto2=true; break ;}
  86.                 KWList.setElementAt(tempa1,i+1);
  87.                 KWPtr.setElementAt(tempb1,i+1);
  88.               }  //end loop-11
  89.             
  90.               if(!goto2)i=0;
  91.               goto2=false;
  92. //label 2:
  93.               KWList.setElementAt(a,i+1);
  94.               KWPtr.setElementAt(b,i+1);
  95.  
  96.             }  //end loop-12
  97.  
  98.             if(jstack==0)return;
  99.             ir=istack[jstack];
  100.             l=istack[jstack-1];
  101.             jstack=jstack-2;
  102.           }else{                                //if(ir-l<m)
  103.             k=(l+ir)/2;
  104.             tempa=KWList.elementAt(k).toString();
  105.             tempa1=KWList.elementAt(l+1).toString();
  106.             KWList.setElementAt(tempa1,k);
  107.             KWList.setElementAt(tempa,l+1);
  108.             tempb=KWPtr.elementAt(k).toString();
  109.             tempb1=KWPtr.elementAt(l+1).toString();
  110.             KWPtr.setElementAt(tempb1,k);
  111.             KWPtr.setElementAt(tempb,l+1);
  112.  
  113.  
  114.             tempa=KWList.elementAt(l+1).toString();
  115.             tempa1=KWList.elementAt(ir).toString();
  116.             if(tempa.compareTo(tempa1)>0){
  117.  
  118.               KWList.setElementAt(tempa1,l+1);
  119.               KWList.setElementAt(tempa,ir);
  120.               tempb=KWPtr.elementAt(l+1).toString();
  121.               tempb1=KWPtr.elementAt(ir).toString();
  122.               KWPtr.setElementAt(tempb1,l+1);
  123.               KWPtr.setElementAt(tempb,ir);
  124.             } //endif(tempa.compareTo(tempa1)>0)
  125.  
  126.  
  127.             tempa=KWList.elementAt(l).toString();
  128.             tempa1=KWList.elementAt(ir).toString();
  129.             if(tempa.compareTo(tempa1)>0){
  130.  
  131.               KWList.setElementAt(tempa1,l);
  132.               KWList.setElementAt(tempa,ir);
  133.               tempb=KWPtr.elementAt(l).toString();
  134.               tempb1=KWPtr.elementAt(ir).toString();
  135.               KWPtr.setElementAt(tempb1,l);
  136.               KWPtr.setElementAt(tempb,ir);
  137.             } //endif(tempa.compareTo(tempa1)>0);
  138.  
  139.  
  140.             tempa=KWList.elementAt(l+1).toString();
  141.             tempa1=KWList.elementAt(l).toString();
  142.             if(tempa.compareTo(tempa1)>0){
  143.  
  144.               KWList.setElementAt(tempa1,l+1);
  145.               KWList.setElementAt(tempa,l);
  146.               tempb=KWPtr.elementAt(l+1).toString();
  147.               tempb1=KWPtr.elementAt(l).toString();
  148.               KWPtr.setElementAt(tempb1,l+1);
  149.               KWPtr.setElementAt(tempb,l);
  150.             } //endif(tempa.compareTo(tempa1)>0)
  151.  
  152.  
  153.             i=l+1;
  154.             j=ir;
  155.             a=KWList.elementAt(l).toString();
  156.             b=KWPtr.elementAt(l).toString();
  157.  
  158.  
  159.             do{                         //loop-3
  160.              loop3=true;
  161.              do{
  162.                i=i+1;
  163.                tempa1=KWList.elementAt(i).toString();
  164.              }while(tempa1.compareTo(a)<0);
  165.      
  166.              do{
  167.                j=j-1;
  168.                tempa1=KWList.elementAt(j).toString();
  169.              }while(tempa1.compareTo(a)>0);
  170.           
  171.              if(j>=i){                
  172.                 tempa=KWList.elementAt(i).toString();
  173.                 tempa1=KWList.elementAt(j).toString();
  174.                 KWList.setElementAt(tempa1,i);
  175.                 KWList.setElementAt(tempa,j);
  176.                 tempb=KWPtr.elementAt(i).toString();
  177.                 tempb1=KWPtr.elementAt(j).toString();
  178.                 KWPtr.setElementAt(tempb1,i);
  179.                 KWPtr.setElementAt(tempb,j);
  180.                 loop3=true;
  181.              }else{
  182.                 loop3=false;             //j<i
  183.              }                           //endif(j>=i)
  184.  
  185.             } while(loop3);              //enddo loop3
  186.  
  187. //label 5
  188.             tempa1=KWList.elementAt(j).toString();
  189.             KWList.setElementAt(tempa1,l);
  190.             KWList.setElementAt(a,j);
  191.             tempb1=KWPtr.elementAt(j).toString();
  192.             KWPtr.setElementAt(tempb1,l);
  193.             KWPtr.setElementAt(b,j);
  194.  
  195.             jstack=jstack+2;
  196.             if(jstack > nstack){
  197.               System.out.println("SORT2: NSTACK too small");
  198.               System.exit(1);
  199.             }
  200.  
  201.             if(ir-i+1 >= j-l){
  202.               istack[jstack]=ir;
  203.               istack[jstack-1]=i;
  204.               ir=j-1;
  205.             }else{
  206.               istack[jstack]=j-1;
  207.               istack[jstack-1]=l;
  208.               l=i;
  209.             }//endif(ir-i+1 >= j-l)
  210.  
  211.           } // endif(ir-l<m)
  212.         } //end while(true)
  213.  
  214.     } //end Sort2 routine
  215.  
  216.   
  217. //========================================================================
  218. //Get the arrays and the # of entries in there.
  219.  
  220.   static void GetKWs (String KWFile){
  221.     String line;
  222.     DataInputStream File = null;
  223.     try{
  224.       File = new DataInputStream(new FileInputStream(KWFile));
  225.     }catch (IOException e){
  226.       System.out.println("SORT: Error Opening the input List "
  227.       +KWFile+" during read.");
  228.       S